#include <iostream>
using namespace std;
int getDigitSum(int nums)
{
    int sums=0;
    while(nums>0)
    {
        sums+=nums%10;
        nums/=10;
    }
    return sums;
}
bool check(int threshold,int rows,int cols,int row,int col,bool*visited)
{
    if(row>=0&&row<rows&&col>=0&&col<cols&&getDigitSum(row)+getDigitSum(col)<=threshold&&!visited[row*cols+col])
        return true;
    else
        return false;
}
int movingCountCore(int threshold,int rows,int cols,int row,int col,bool *visited)
{
    int count = 0;

    if(check(threshold,rows,cols,row,col,visited))
    {
        visited[row*cols+col] = true;
        count = 1 + movingCountCore(threshold,rows,cols,row-1,col,visited)
                + movingCountCore(threshold,rows,cols,row+1,col,visited)
                + movingCountCore(threshold,rows,cols,row,col-1,visited)
                + movingCountCore(threshold,rows,cols,row,col+1,visited);
    }
    cout<<"当前位置,row:"<<row<<" col:"<<col<<endl;
    return count;
}
int movingCount(int threshold,int rows,int cols)
{
    if(threshold<0||rows<=0||cols<=0)
        return 0;
    bool *visited = new bool[rows*cols];
    for(int i=0;i<rows*cols;++i)
    {
        visited[i] = false;
    }
    int count = movingCountCore(threshold,rows,cols,0,0,visited);
    cout<<"访问的格子数目为:"<<count;
    return count;
}

int main()
{
    int threshold=18,rows=5,cols=5;
    int count = movingCount(threshold,rows,cols);
    return 0;
}

